MinCaml のコードリーディング
min-camllで書いたプログラムを動くようにしたい。どのへんを修正すればいいのか調べるため、min-camlのソースを読んでみる。
コンパイラの各ステップの説明がある
file (* ファイルをコンパイルしてファイルに出力する (caml2html: main_file) *)
lexbuf (* バッファをコンパイルしてチャンネルへ出力する (caml2html: main_lexbuf) *)
Lexer 字句解析
Parser 構文解析
val exp : (Lexing.lexbuf -> token) -> Lexing.lexbuf -> Syntax.t
Typing 型推論
val f : Syntax.t -> Syntax.t
型推論とは？
普通のMLと同様に、MinCamlでは変数や関数の型を書かなくても自動で推論してくれます。これを型推論といい、多相関数や高階関数のあるプログラムでは非常に便利です。
MinCamlの型推論の本体は関数Typing.gです。この関数は、型環境（変数の名前から、その型への写像）envと、式eとを受け取り、eの型を推論して返します。また、式の中に出てくる変数の型が合っているかどうかも調べます。もし未定義の型変数があったら、適切な型を代入します。このような代入により型を合わせる関数がTyping.unifyです。
KNormal K正規化
val f : Syntax.t -> t
K正規化とは？
「コンパイルとは高水準言語と低水準言語のギャップを埋めることである」と述べましたが、そのようなギャップの一つに「ネストした式」がありました。たとえばMLや大概の言語ではa + b + c - dのような式の値を一発で計算することができますが、普通のアセンブリにそのような命令はありません。
このギャップを埋めるために、計算の途中結果もすべて変数として定義するのがK正規化という変換です（ちなみにK正規化という名前は、ML Kitというコンパイラに由来します）。たとえば、さっきの例は
let tmp1 = a + b in
let tmp2 = tmp1 + c in
tmp2 - d
という風に変換できます。
Alpha アルファ変換
val f : KNormal.t -> KNormal.t
アルファ変換とは？
その前に「異なる変数には異なる名前をつける」α変換を行います。違う変数に同じ名前がついていると、いろいろと処理が面倒になるためです。たとえばlet x = 123 in let x = 456 in x + xという式だったら、let x1 = 123 in let x2 = 456 in x2 + x2と直してしまいます。
iter (* 最適化処理をくりかえす (caml2html: main_iter) *)
Beta ベータ簡約
val f : KNormal.t -> KNormal.t
Assoc
val f : KNormal.t -> KNormal.t
Inline インライン展開
val f : KNormal.t -> KNormal.t
ConstFold 定数の畳み込み
val f : KNormal.t -> KNormal.t
Elim 不要定義削除
val f : KNormal.t -> KNormal.t
Closure クロージャ変換
val f : KNormal.t -> prog
参考：クロージャ変換
Virtual 仮想マシンコード生成（*** 要修正 / 【必須】 ***）
val f : Closure.prog -> Asm.prog
参考：仮想機械
Simm 13bit即値最適化（*** 要修正 / 最適化なので無くても動く ***）
val f : Asm.prog -> Asm.prog
RegAlloc レジスタ割り当て（*** 要修正 / ここを修正しないとレジスタに変数を割り当てできない ***）
val f : Asm.prog -> Asm.prog
参考: レジスタ割付け
Emit アセンブリ生成（*** 要修正 / 【必須】 ***）
val f : out_channel -> Asm.prog -> unit
要修正箇所
（*** 要修正 ***）の箇所はCPUごとに変更が必要になる
CPUごとの差異（ppcとx86）
asm.ml
asm.mli
emit.ml
libmincaml.S
regAlloc.ml
simm.ml
virtual.ml
要修正箇所
必須
virtual.ml（仮想マシンコード生成）
emit.ml（アセンブリ生成）
regAlloc.ml（レジスタ割り当て）
最適化なので後回しでも良さそう
simm.ml （13bit即値最適化）
（引数に渡されたものをそのまま返すように修正する必要はある）
Parser 構文解析
パースした結果の構文木を Syntax.t の形式で返す
code:sytax.ml
(* Syntax.t *)
type t = (* MinCamlの構文を表現するデータ型 (caml2html: syntax_t) *)
| Unit
| Bool of bool
| Int of int
| Float of float
| Not of t
| Neg of t
| Add of t * t
| Sub of t * t
| FNeg of t
| FAdd of t * t
| FSub of t * t
| FMul of t * t
| FDiv of t * t
| Eq of t * t
| LE of t * t
| If of t * t * t
| Let of (Id.t * Type.t) * t * t
| Var of Id.t
| LetRec of fundef * t
| App of t * t list
| Tuple of t list
| LetTuple of (Id.t * Type.t) list * t * t
| Array of t * t
| Get of t * t
| Put of t * t * t
and fundef = { name : Id.t * Type.t; args : (Id.t * Type.t) list; body : t }
parser.mly
よく分からん要素
App （Applyかな？）
exp args
Get
.(exp)
Put
.(exp) <-
Typing 型推論